The invention relates generally to the analysis of surfaces and to surface parameterizations, and in particular, to an improved method, apparatus, and article of manufacture for repairing, matching and establishing a correspondence function between two three dimensional surfaces of arbitrary genus that implements global parameterization of the surfaces and maps them both onto a 2D plane.
As known in the analysis of geometric surfaces, a “correspondence” between two surfaces is a function that maps one surface onto the other. A “genus” means the number of holes in the surface. FIG. 1 shows example 3D objects 15a-15b each of a respective indicated genus 12 that is greater than 1 as depicted.
However, currently, there is no way to establish a correspondence function in two dimensions between two three dimensional surfaces of arbitrary genus, that can be used for data fitting, morphing, and mapping textures between surfaces. Moreover, there is no way to map two three dimensional surfaces of arbitrary genus into two dimensions that can be used to match two (2) three-dimensional (3D) surfaces of arbitrary genus for use in 3D object recognition, shape registration, and classification applications. Performing the operation in two dimensions results in a number of benefits including faster processing than in three dimensions.
One class of methods in 3D surface correspondence use parameterizations of meshes over a common parameter domain to establish a direct correspondence between them. These methods either typically require user supplied feature correspondences such as described in the reference to A. Lee, D. Dobkin, W. Sweldens, and P. Shroder entitled “Multiresolution mesh morphing”, in Proceedings of SIGGRAPH 99 (August 1999), Computer Graphics Proceedings, Annual Conference Series, pp. 343-350 and, in the reference to E. Praun, W. Sweldens, and P. Shroder entitled “Consistent mesh parameterizations” in Proceedings of ACM SIGGRAPH 2001 (August 2001), Computer Graphics Proceedings, Annual Conference Series, pp. 179-184 (both incorporated by reference) or, have complex algorithms to properly align the selected features during the parameterization process (see, e.g., the reference to V. Kraevoy and A. Sheffer entitled “Cross-parameterization and compatible remeshing of 3D models” in ACM Transactions on Graphics 23, 3 (August 2004), 861-869 and, the reference to J. Schreiner, A. Asirvatham and E. Praun entitled “Inter-surface mapping” ACM Transactions on Graphics 23, 3, 2004, pp 179-184, both incorporated by reference). Furthermore, the combinatoric complexity of the input meshes determines the performance of these methods, which can be quite costly (on the order of hours). The final matching can only be controlled by changing the parameteric domain layout.
Another class of methods matches a template surface to range scan data directly in 3D such as described in the reference to B Allen, B. Curless and Z. Popovic entitled “The space of human body shapes: reconstruction and parameterization from range scans” in ACM Transactions on Graphics 22, 3 (July 2003), 587-594 and in the reference to L. Zhang, N. Snavely, B. Curless and S. M. Seitz entitled “Spacetime faces: high resolution capture for modeling and animation” in ACM Transactions on Graphics 23, 3 (August 2004), 548-558. These algorithms require manual 3D alignment and the surfaces must be in similar poses in order to accurately match them on the basis of surface normals.
One known approach proposes a fast multiresolution strategy to match 3D surfaces by mapping the surfaces to the 2D domain and applies well-established matching methods from image processing in the parameter domains of the surfaces (See, e.g., the reference to Nathan Litke, Marc Droske, Martin Rumpf and Peter Schröder entitled “An Image Processing Approach to Surface Matching” in Proceedings of the Symposium on Geometry Processing 2005). This approach has one major limitation: This technique assumes that the surfaces to be matched must be homeomorphic to a disk. A significant number of additional and non-obvious algorithmic steps would be necessary to apply this technique to determine correspondences between surfaces of arbitrary genus.
A large body of work in shape matching is devoted to the concept of developing shape descriptors. The general approach of these methods is to define a mapping from the space of models into a fixed dimensional vector space, and then to define the measure of similarity between two models as the distance between their corresponding descriptors. Shape descriptor methods allow a correspondence-based measure of similarity to be obtained without the overhead of explicitly establishing the correspondences. While 2D shapes have a natural arc length parameterization, 3D surfaces of arbitrary genus do not. As a result, common shape descriptors for 2D contours cannot be extended to 3D surfaces, and computationally efficient matching algorithms based on dynamic programming cannot be applied to 3D objects. Another problem is the higher dimensionality of 3D data, which makes registration, finding feature correspondences, and fitting model parameters more expensive. As a result, methods that match shapes using geometric hashing or deformations are more difficult in 3D.
One major challenge that 3D shape descriptor approaches have to address is that a 3D model and its images under a similarity transformation are considered to be the same in 3D shape matching. 3D Shape matching techniques based on shape descriptors have to as a result of this make adjustments in two possible ways: (1) Choose a mapping that is invariant to similarity transformation, so that the same shape descriptor is defined for every orientation of the model; and, (2) Compute the shape descriptor of an alignment normalized version of the model by normalization that is accomplished by placing the model into its own canonical coordinate system. Obtaining rotationally invariant representations is a known technique. A method to separate anisotropy from the shape matching equation is known, however, the method does not work well for highly anisotropic models.
Existing methods for 3D shape matching that rely on local shape signatures include curvature-based shape representations, regional point representations, shape distributions, spline representations and harmonic shape images. Such shape representations that use local shape signatures are not stable, sensitive to resolution changes, and do not perform well in the face of occlusion and noise.
Due to the difficulty of the 3D shape matching problem, several known methods reduce the problem to a 2D image matching problem. Zhang et al. propose harmonic maps for surface matching (See Zhang et al. reference entitled “Harmonic maps and their applications in surface matching”. In CVPR99, pages 524-530). Wang et al., in their reference entitled “High resolution tracking of non-rigid 3d motion of densely sampled data using harmonic maps” in ICCV05, pages I: 388-395 (2005), use harmonic maps to track dynamic 3D surfaces. There is a large body of work on conformal maps for face and brain surface matching. Sharon et al., in their reference entitled “2d-shape analysis using conformal mapping” in CVPR04, pages II: 350-357, (2004) describes a method for analyzing similarities of 2D shapes using conformal maps. The main drawback of these solutions is that in order to calculate harmonic maps, the surface boundary needs to be identified, and a boundary mapping from 3D surfaces to the 2D domain needs to be created.
Some techniques do not require boundary information. For example, the technique described in references to Wang et al. entitled “Conformal Geometry and Its Applications on 3D Shape Matching Recognition, and Stitching” in IEEE Trans. Pattern Anal. Mach. Intell. 29(7): 1209-1220 (2007) and, entitled “3D Surface Matching and Recognition Using Conformal Geometry” in CVPR (2) 2006: 2453-2460 makes use of conformal geometry theory and maps the 3D surface to the 2D plane through a global optimization. The main limitation of this technique is that it is applicable only to surfaces homeomorphic to a disk. The method does not address the case when the input surfaces to be matched are of genus greater than one, and it will fail to correctly compute a matching if applied as is.
Thus, it would be highly desirable to provide a system and method for matching and establishing correspondences between three dimensional surfaces of arbitrary genus and topology in two dimensions.